#include<bits/stdc++.h>
using namespace std;

class Solution {
private:
    void division(vector<int>& arr, int low, int high, int k){ // 除了回溯部分基本跟快排一样
        if(low >= high)return;
        int i = low, j = high;
        swap(arr[i], arr[(i + j) / 2]);
        int key = arr[i];
        while(i < j){
            while(i < j && arr[j] > key)j--;
            arr[i] = arr[j];
            while(i < j && arr[i] <= key)i++;
            arr[j] = arr[i];
        }
        arr[i] = key;
        if(i - low + 1 == k)return;
        if(i - low + 1 < k)division(arr, i + 1, high, k - i + low - 1);
        else division(arr, low, i - 1, k);
    }
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        division(arr, 0, arr.size() - 1, k);
        vector<int> ans;
        for(int i = 0; i < k; i++)ans.push_back(arr[i]);
        return ans;
    }
};

/**
 * 2021.9.3
 * 基于快排思想，但是每走完一趟快排以后，不是两侧回溯而是根据基准值的位置进入
 * 假设一趟快排后基准值的位置为 t (从 1 开始为第一个数)  
 * 如果 t == k 说明 1 ~ t 的位置刚好是前 k 个小的数
 * 如果 t > k 说明要从 [low, t - 1] 这些位置选出 k 个小的数
 * 如果 t < k 说明已经选出了 t 个比较小的数，还需要从 [t + 1, high] 选出 k - t 个比较小的数。
 */